class UnionFind:
    """并查集实现，用于文档分组"""
    
    def __init__(self):
        self.parent = {}
        self.rank = {}
    
    def add(self, x):
        """添加元素"""
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 0

    def find(self, x):
        """查找根节点（带路径压缩）"""
        if x not in self.parent:
            return x
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        """合并两个集合"""
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x != root_y:
            # 按秩合并
            if self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            elif self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
